1. Field of the Invention
The invention relates in general to a decompression circuit, and more particularly to a Lempel-Ziv-Markov chain-Algorithm (LZMA) decompression circuit and associated decompression method.
2. Description of the Related Art
In a decompression operation using the Lempel-Ziv-Markov chain-Algorithm (LZMA), a repeating string is compressed into a distance-length pair. For example, a string “ABCDABCE” is compressed into “A, B, C, D, (4, 3), E”, where (4, 3) is referred to as a distance-length pair that represents first three literals (i.e., A, B, and C, “length”) of four previous literals (distance). Another compression operation is then performed to generate compressed data. In a decompression process, the compressed data is decompressed, by binary arithmetic coding (BAC), into “A, B, C, D, (4, 3), E”, which is then restored to “ABCDABCE” using an LZ77 decompression operation. When decompressing a next literal (commonly referred to as “delta literal”, which is “E” in this example) of the length-distance pair using the BAC method, a previous literal (the 7th literal “C” in this example) and the next literal (the 4th literal “D” in this example) of the string corresponding to the distance-length pair are used. Therefore, when decompressing “E” using the BAC method, “C” and “D” can only be provided to a front-end for the BAC decompression after the distance-length pair (4, 3) is decompressed by the LZ77 operation, leading to reduced decompression efficiency. Further, compression/decompression utilizing the LZMA method is all implemented through software.